package com.example.question.dp.dp1;

import java.util.ArrayList;
import java.util.List;

/**
 * 分割回文串
 *
 * @link {<a href="https://leetcode.cn/problems/palindrome-partitioning/">...</a>}
 * 解法一：暴力递归
 * 解法二：记忆化搜索！ 这个仔细思考思考！
 */
public class Code07_131 {
    private int count = 0;

    public static void main(String[] args) {
        Code07_131 code = new Code07_131();
        System.out.println("code.partition(\"aab\") = " + code.partition("aabbc"));
        System.out.println(code.count);
    }

    char[] chars = null;

    public List<List<String>> partition(String s) {
        chars = s.toCharArray();
        List<List<String>> result = new ArrayList<>();
        Boolean[][] dp = new Boolean[s.length()][s.length()];
        dfs(s, 0, dp, new ArrayList<>(), result);
        return result;
    }

    /**
     * 对于“aabbc”字符串 加了记忆化搜索的之后计算了七次，对于未加记忆化搜索 计算了十三次
     */
    private void dfs(String s, Integer startIndex, Boolean[][] dp, List<String> path, List<List<String>> result) {
        if (startIndex == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (startIndex > s.length()) {
            return;
        }
        for (int len = 1; len <= s.length(); len++) {
            // substring(i,j) 是取到j-1的 因此需要取到算到边界值
            if (len + startIndex <= s.length()) {
                String str = s.substring(startIndex, startIndex + len);
                // 记忆化搜索 减少重复计算
                if (dp[startIndex][startIndex + len - 1] == null) {
                    dp[startIndex][startIndex + len - 1] = isPalindrome(startIndex, startIndex + len - 1);
                }
                if (dp[startIndex][startIndex + len - 1]) {
                    path.add(str);
                    dfs(s, startIndex + len, dp, path, result);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    public boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (chars[left] != chars[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
